package A一周刷爆LeetCode.A基础班.A基础;

/**
 * @author wei.zhao
 * @description: 异或运算应用
 * @date 2022年01月07日 10:53
 */
public class 异或运算 {

    public static void main(String[] args) {
        test01();
        test02(new int[]{1, 2, 2, 1, 3, 7, 3});
        test03(new int[]{1, 2, 2, 1, 3, 7, 3, 9, 11, 13, 11, 13});
    }

    /**
     * 不用额外变量交换两个数
     */
    public static void test01() {
        int a = 10, b = 100;
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println(a);
        System.out.println(b);
    }

    /**
     * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数
     */
    public static void test02(int[] arr) {
        int result = 0;
        for (int i : arr) {
            result ^= i;
        }
        System.out.println("出现奇数次的数字是：" + result);
    }

    /**
     * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个。
     * 解题思路：
     * 假设这两个数是a、b
     * 1.将这些数异或之后肯定等与a^b
     * 2.因为a、b肯定不相等，所以a^b肯定在某一位上不等于1，a、b在这个位置上值不同，找出这个位置，其他位置全部置为0
     * 3.由此可以分组，所有&上这个数为0的值求异或，答案就是a的值
     * 4.a^b^a就是a的值
     */
    public static void test03(int[] arr) {
        //所有数异或结果
        int temp1 = 0;
        int a = 0;
        int b = 0;
        for (int i : arr) {
            temp1 ^= i;
        }
        //求出第一个不等于0的位，其他位全部置为0
        int temp2 = temp1 & (~temp1 + 1);
        for (int i : arr) {
            if ((i & temp2) == 0) {
                a ^= i;
            }
        }
        b = temp1 ^ a;
        System.out.println("出现奇数次的两个数是：" + a + "和" + b);
    }

}
